﻿using System;
using System.Diagnostics;

namespace MaxHeap
{
    class Program
    {
        static void Main(string[] args)
        {



            int n = 100000;

            MaxHeap<int> maxHeap = new MaxHeap<int>();
            Random random = new Random();
            for (int i = 0; i < n; i++)
                maxHeap.add(random.Next(1000000));

            int[] arr = new int[n];
            for (int i = 0; i < n; i++)
                arr[i] = maxHeap.extractMax();

            for (int i = 1; i < n; i++)
                if (arr[i - 1] < arr[i])
                    throw new Exception("Error");

            Console.WriteLine("Test MaxHeap completed.");
            Console.WriteLine();
            Console.WriteLine();

            //测试 heapify：数组转换成堆
            int[] testData = new int[n];
            for (int i = 0; i < n; i++)
                testData[i] = random.Next(1000000);

            double time1 = testHeap(testData, false);
            Console.WriteLine("Without heapify: " + time1 + " s");

            double time2 = testHeap(testData, true);
            Console.WriteLine("With heapify: " + time2 + " s");

        }

        private static double testHeap(int[] testData, bool isHeapify)
        {

            Stopwatch timer = new Stopwatch();

            timer.Start();

            MaxHeap<int> maxHeap;
            if (isHeapify)
                maxHeap = new MaxHeap<int>(testData);
            else
            {
                maxHeap = new MaxHeap<int>();
                foreach (int num in testData)
                    maxHeap.add(num);
            }

            int[] arr = new int[testData.Length];
            for (int i = 0; i < testData.Length; i++)
                arr[i] = maxHeap.extractMax();

            for (int i = 1; i < testData.Length; i++)
                if (arr[i - 1] < arr[i])
                    throw new Exception("Error");
            Console.WriteLine("Test MaxHeap completed.");

            timer.Stop();

            return timer.Elapsed.TotalSeconds;
        }

    }
}
